package com.example.myletcodelearing.one

import com.example.myletcodelearing.kmp.KmpTest
import java.util.*
import kotlin.collections.ArrayList
import kotlin.math.max

/**
 * @author tgw
 * @date 2022/9/30
 * @describe
 */
fun main(array: Array<String>) {
    val num1 = intArrayOf()
    val num2 = intArrayOf(3)
    val ss = "abcabcbb"
    var length = Solution4().findMedianSortedArrays(num1, num2)
    var length2 = Solution4().findMedianSortedArrays2(num1, num2)

    print("中位数：$length")
    print("中位数官方解法：$length2")

}

private class Solution4 {
    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        var num3 = ArrayList<Int>()
        var index1 = 0
        var index2 = 0
        while (index1 < nums1.size) {
            for (n2 in index2 until nums2.size) {
                if (nums1[index1] > nums2[n2]) {
                    num3.add(nums2[n2])
                    index2++

                } else {
                    num3.add(nums1[index1])
                    index1++
                }
                break
            }
            if (index2>=nums2.size){
                num3.add(nums1[index1])
                index1++
            }
        }
        while (index2 < nums2.size) {
            num3.add(nums2[index2])
            index2++
        }
        var size = num3.size
        var num=0.0
        if (size%2 !=1){
            num = ((num3[size/2-1]+num3[size/2]).toDouble()/2)
        }else{
            num = num3[((size-1)/2)].toDouble()
        }
        return num
    }


    fun findMedianSortedArrays2(nums1: IntArray, nums2: IntArray): Double {
        val m = nums1.size
        val n = nums2.size
        val left = (m + n + 1) / 2
        val right = (m + n + 2) / 2
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0
    }

    //i: nums1的起始位置 j: nums2的起始位置
    fun findKth(nums1: IntArray, i: Int, nums2: IntArray, j: Int, k: Int): Int {
        if (i >= nums1.size) return nums2[j + k - 1] //nums1为空数组
        if (j >= nums2.size) return nums1[i + k - 1] //nums2为空数组
        if (k == 1) {
            return Math.min(nums1[i], nums2[j])
        }
        val midVal1 = if (i + k / 2 - 1 < nums1.size) nums1[i + k / 2 - 1] else Int.MAX_VALUE
        val midVal2 = if (j + k / 2 - 1 < nums2.size) nums2[j + k / 2 - 1] else Int.MAX_VALUE
        return if (midVal1 < midVal2) {
            findKth(nums1, i + k / 2, nums2, j, k - k / 2)
        } else {
            findKth(nums1, i, nums2, j + k / 2, k - k / 2)
        }
    }
}